package hot;

import java.util.Stack;

public class basi {
    public static int largestRectangleArea(int[] nums) {
//        if(nums.length==0){
//            return 0;
//        }
//        int n=nums.length;
//        int max=0;
//        for(int i=0;i<n;i++){
//            // 找左边最后一个大于等于nums[i]的 此时的坐标
//            int left=i;
//            while(left>=1&&nums[left-1]>=nums[i]){
//                left--;
//
//            }
//            int right=i;
//            while(right<=n-2&&nums[right+1]>=nums[i]){
//                right++;
//
//            }
//            max=Math.max(max,(right-left+1)*nums[i]);
//        }
//        return max;
        int n = nums.length;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);  // 预存哨兵值-1
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            // 当前柱子比栈顶柱子矮时，计算面积
            while (stack.peek() != -1 && nums[i] < nums[stack.peek()]) {
                int height = nums[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        // 处理栈中剩余的柱子
        while (stack.peek() != -1) {
            int height = nums[stack.pop()];
            int width = n - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }

        return maxArea;
    }

    public static void main(String[] args) {
        int[] nums={3,1,3,2,2};
        int i = largestRectangleArea(nums);
        System.out.println(i);
    }
}
